### 数值上指针法的练习：
# 1.80. 删除有序数组中的重复项 II | 力扣 | LeetCode |  🟠
# 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
# 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
# 思路：和之前去除重复元素一样，只不过需要维护一个计数的参数：
# 咩，我感觉之前的方法我没有完全理解：有序是很重要的一个特征 ❓❓ ⭐⭐ 没太理解
# 就是说nums[slow]用来存这个符合条件的值，然后fast它的作用就是扫描这个表！！！ clever me
class Delete_Duplicates2(object):
    def solution(self,nums):
        # 边遍历边改，一个慢指针，一个快指针：
        # 快慢指针，维护 nums[0..slow] 为结果子数组
        slow = 0
        fast = 0
        # 记录一个元素重复的次数
        count = 0
        while fast < len(nums):
            if nums[fast] != nums[slow]:
                # 此时，对于 nums[0..slow] 来说，nums[fast] 是一个新的元素，加进来
                slow += 1
                nums[slow] = nums[fast]
            elif slow < fast and count < 2: #这里为什么需要slow<fast? -> slow < fast且count的时候才说明遇到多个重复元素，否则可能是指在一个元素
                # 此时，对于 nums[0..slow] 来说，nums[fast] 重复次数小于 2，也加进来
                slow += 1
                nums[slow] = nums[fast]
            fast += 1
            count += 1
            if fast < len(nums) and nums[fast] != nums[fast - 1]:
                # fast 遇到新的不同的元素时，重置 count
                count = 0
        # 数组长度为索引 + 1
        return nums # nums
    def test(self):
        nums=[1,2,2,2,3,5,6,6,7]
        res = self.solution(nums)
        print('结果是：',res)

# 2. 125. 验证回文串 | 力扣 | LeetCode |  🟢
# 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
# 字母和数字都属于字母数字字符。
# 给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false
# 很简单
class check_Palindrome(object):
    def solution(self,s):
        s=s.replace(" ","") #删除所有空格
        s=s.lower()
        i,j=0,len(s)-1
        while i<=j:
            if s[i]!=s[j]:
                return False
            i+=1
            j-=1
        return True
    def test(self):
        s='aBcd d d Cba' # abcddcba
        print(self.solution(s))

# 3. 75. 颜色分类 | 力扣 | LeetCode |  🟠
# 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
# 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
# 必须在不使用库内置的 sort 函数的情况下解决这个问题。
# 某个排序算法,简单
class SortColor(object):
    def solution(self,nums):
        for i in range(len(nums)):
            for j in range(i,len(nums)):
                if nums[i]>nums[j]:
                    temp=nums[i]
                    nums[i]=nums[j]
                    nums[j]=temp
        return nums
    def test(self):
        nums=[1,2,0,0,2,1,1,2,0]
        print(self.solution(nums))

# 4. 88. 合并两个有序数组 | 力扣 | LeetCode |  🟢
# 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
# 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
# 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，
# 其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
# 思路：从后面开始开始遍历的两个指针, 简单, 小技巧
# 思路1： 将2添加到1里再原地排序就可以（使用上一题的办法）
class MergeList(object):
    def solution(self,nums1,nums2,m,n):
        i,j=m-1,n-1
        k=m+n-1
        while i>=0 and j>=0:
            if nums1[i]>=nums2[j]:
                nums1[k]=nums1[i]
                i-=1
            else:
                nums1[k]=nums2[j]
                j-=1
            k-=1
        # 考虑j可能没有走完：
        while j>=0:
            nums1[k]=nums2[j]
            j-=1
            k-=1
        return nums1
    def test(self):
        nums1=[2,0]
        m=1
        nums2=[1]
        n=1
        print(self.solution(nums1,nums2,m,n))

# 5. 977. 有序数组的平方 | 力扣 | LeetCode |  🟢
# 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
# 主要需要考虑负数：
# 考虑设计时间复杂度为 O(n)的解答方法
# 思路：考虑使用两个指针，头尾，比对绝对值/平方值来判断
# [-9,-5,1,6,8] 注意边界条件
class SquareList(object):
    def solution(self,nums):
        res=[0]*(len(nums))
        i,j=0,len(nums)-1
        k=len(nums)-1
        while i<=j: # 以0为界限，分开正负数
            if nums[i]**2 < nums[j]**2:
                res[k]=(nums[j]**2)
                j-=1
            else:
                res[k]=(nums[i]**2)
                i+=1
            k-=1
        return res
    def solution(self,nums1,nums2,m,n):
        pass
    def test(self):
        nums1=[1,2,5,6,8,8,11]
        m=7
        nums2=[0,2,2,4,5,5,8,44]
        n=8
        print(self.solution(nums1,nums2,m,n))
        nums=[-1]
        print(self.solution(nums))

# 5. 1329. 将矩阵按对角线排序 | 力扣 | LeetCode |  🟠
# 矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线，沿右下方向一直到矩阵末尾的元素。
# 例如，矩阵 mat 有 6 行 3 列，从 mat[2][0] 开始的 矩阵对角线 将会经过 mat[2][0]、mat[3][1] 和 mat[4][2] 。
# 给你一个 m * n 的整数矩阵 mat ，请你将同一条 矩阵对角线 上的元素按升序排序后，返回排好序的矩阵。
# 难点：
# 1. 规律：同一个对角线上的元素的索引差值是一样的
# 2. 如何存储中间结果和还原回矩阵？
class SortDiagonalElements(object):
    def solution(self,mat):
        # 用字典存数据：
        m=len(mat)
        n=len(mat[0])
        res = [[0 for _ in range(n)] for _ in range(m)] # !!! 不能用乘法！ 要用列表推导表达式
        dicts={}
        for i in range(m):
            for j in range(n):
                if i-j not in dicts:
                    dicts[i-j]=[]
                dicts[i-j].append(mat[i][j])
        for values in dicts.values():
            values.sort(reverse=True)
        for i in range(m):
            for j in range(n):
                res[i][j]=dicts[i-j].pop()
        return res
    def test(self):
        mat=[[2,3,5,6],
                [2,1,5,8],
                [4,1,9,3]]
        print(self.solution(mat))

# 6. 1260. 二维网格迁移 | 力扣 | LeetCode |  🟢
# 给你一个 m 行 n 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。
# 每次「迁移」操作将会引发下述活动：
# 位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]。
# 位于 grid[i][n - 1] 的元素将会移动到 grid[i + 1][0]。
# 位于 grid[m - 1][n - 1] 的元素将会移动到 grid[0][0]。
# 请你返回 k 次迁移操作后最终得到的 二维网格。
# 思路，推导后发现上述的3个操作，是一次性的结果，（其实人家的字面意思说的很清楚了）；可以硬写，但是需要存储空间多（每次都需要一个空的list(list)）
class TDListMove(object):
    def solution(self,grid:List[List], k)-> List[List]:
        m,n=len(grid),len(grid[0])
        def operation(input):
            save = [[0 for _ in range(n)] for _ in range(m)]
            for i in range(m):
                for j in range(n):
                    if j-1>=0:
                        save[i][j]=input[i][j-1]
            for i in range(m):
                if i+1<m:
                    save[i+1][0]=input[i][n-1]
            save[0][0]=input[m-1][n-1]
            return save
        input = grid
        for opt in range(k):
            input = operation(input)
        return input
    def solution_fast(self,gird:List[List],k)-> List[List]:
        # 这题目的实际操作是从头到尾连接元素后把最后一个元素放前面然后重新组合matrix
        # 这样的话可以优化的就是k次循环可以直接从这个规律里被优化成一次循环.
        mid1,mid2=[],[]
        m,n=len(gird),len(gird[0])
        res = [[0 for _ in range(n)] for _ in range(m)]
        count=0
        for i in range(m):
            for j in range(n):
                if count<k:
                    mid1.append(gird[i][j])
                else:
                    mid2.append(gird[i][j])
                count+=1
        mid=mid2+mid1
        mid.reverse()
        for i in range(m):
            for j in range(n):
                res[i][j]=mid.pop()
        return res
    def test(self):
        mat=[[3,8,1,9],
             [19,7,2,5],
             [4,6,11,10],
             [12,0,21,13]]
        k=2
        print(self.solution_fast(mat,k))

if __name__ == '__main__':
    TDListMove().test()